package com.xiyou.week03.recursion;

import java.util.ArrayList;
import java.util.List;

/**
 * 77. 组合
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 * <p>
 * 你可以按 任何顺序 返回答案。
 *
 * @ClassName：Combine
 * @Author：西柚
 * @Date：2022/1/11 4:40 下午
 * @Versiion：1.0
 */
public class Combine {

    private int n, k;
    private List<Integer> chosen = new ArrayList<Integer>();
    private List<List<Integer>> ans = new ArrayList<List<Integer>>();

    /**
     * 输入：n = 4, k = 2
     * 输出：[[3, 4], [2, 4], [2, 3], [1, 4], [1, 3], [1, 2]]
     *
     * @param n
     * @param k
     * @return
     */
    public List<List<Integer>> combine(int n, int k) {
        this.n = n;
        this.k = k;
        recur(1);
        return ans;
    }


    private void recur(int i) {
        // 剪枝
        if (chosen.size() > k || chosen.size() + (n - i + 1) < k) {
            return;
        }
        // 递归边界
        if (i == n + 1) {
            // 深拷贝
            ans.add(new ArrayList<Integer>(chosen));
            return;
        }

        // 每层的相似逻辑：i选或者不选
        recur(i + 1);
        chosen.add(i);
        recur(i + 1);
        chosen.remove(chosen.size() - 1);
    }

    public static void main(String[] args) {
        int n = 4, k = 2;

        Combine combine = new Combine();
        System.out.println(combine.combine(n, k));
    }
}
